2055. 蜡烛之间的盘子

算法内容

本文件实现 LeetCode 2055「蜡烛之间的盘子」。目标是对多个区间查询，统计区间内两根蜡烛之间的盘子数量。

代码预处理三个数组：v 为盘子数量前缀和，left[i] 表示位置 i 左侧最近蜡烛下标，right[i] 表示位置 i 右侧最近蜡烛下标。对于查询 [l, r]，先找到 right[l] 和 left[r] 作为区间内最靠内的两根蜡烛，如果左蜡烛在右蜡烛左侧，就用前缀和相减得到盘子数。预处理 O(n)，每次查询 O(1)，总复杂度 O(n + q)。

算法实现

#include<vector>
#include<iostream>
#include<stack>

using namespace std;


class Solution {
public:
    vector<int> platesBetweenCandles(string s, const vector<vector<int>>& queries) {
        int len = s.length();
        vector<int> v(len, 0);
        vector<int> left(len, -1);
        vector<int> right(len, len);
        v[0] = s[0] == '*' ? 1 : 0; 
        int lastLeft = s[0] == '|' ? 0 : -1;
        left[0] = lastLeft;
        for(int i = 1; i < len; i++) {
            int x = s[i] == '*' ? 1 : 0;
            v[i] = v[i-1] + x;
            if(s[i] == '|') {
                lastLeft = i;
            }
            left[i] = lastLeft;
        }
        int lastRight = s[len-1] == '|' ? len-1 : len;
        for(int i = len-2; i >= 0; i--) {
            if(s[i] == '|') {
                lastRight = i;
            }
            right[i] = lastRight;
        }
        vector<int> ans;
        len = queries.size();
        for(int i = 0; i < len; i++) {
            int diff = 0;
            printf("%d, %d\n", right[queries[i][0]], left[queries[i][1]]);
            printf("%d, %d\n", v[right[queries[i][0]]], v[left[queries[i][1]]]);
            if(right[queries[i][0]] < left[queries[i][1]]) {
                diff = v[left[queries[i][1]]] - v[right[queries[i][0]]];
            }
            ans.push_back(diff);
        }
        return ans;
    }
};

int main() {
    Solution s;
    string str = "***|**|*****|**||**|*";
    vector<int> res = s.platesBetweenCandles(str, {{1,17},{4,5},{14,17},{5,11},{15,16}});
    int len = res.size();
    for(int i = 0; i < len; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}